package sort

func quickSort(nums []int, start, end int) {
	l := start
	r := end
	centerValue := nums[(start+end)/2]
	for l < r {
		// 从左边找出比中间元素大的元素
		for nums[l] < centerValue {
			l++
		}
		// 从右边找出比中间元素小的元素
		for nums[r] > centerValue {
			r--
		}
		if l >= r {
			break
		}
		// 交换左边和右边的值
		nums[l], nums[r] = nums[r], nums[l]
		if nums[l] == centerValue {
			r--
		}
		if nums[r] == centerValue {
			l++
		}
	}

	if l == r {
		l++
		r--
	}
	if start < r {
		quickSort(nums, start, r)
	}
	if end > l {
		quickSort(nums, l, end)
	}
}
